#include <queue>
#include "BTree.cpp"
#define MaxSize 100

void PreOrder(BTNode *bt) {
    if (bt != NULL) {
        printf("%c ", bt->data);
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
}

void InOrder(BTNode *bt) {
    if (bt != NULL) {
        InOrder(bt->lchild);
        printf("%c ", bt->data);
        InOrder(bt->rchild);
    }
}

void PostOrder(BTNode *bt) {
    if (bt != NULL) {
        PostOrder(bt->lchild);
        PostOrder(bt->rchild);
        printf("%c ", bt->data);
    }
}

void LevelOrder(BTNode *bt) {
    BTNode *p;
    // 使用 STL 的队列来实现层次遍历
    // 这里使用 std::queue 来存放二叉链结点指针
    std::queue<BTNode *> qu;
    qu.push(bt);	//根结点指针进入队列
    while (!qu.empty()) {	//队列不为空循环
        p = qu.front(); // 获取队头元素
        qu.pop(); // 出队
        printf("%c ", p->data);	//访问该结点
        if (p->lchild != NULL) {	//有左孩子时将其进队
            qu.push(p->lchild);
        }
        if (p->rchild != NULL) {	//有右孩子时将其进队
            qu.push(p->rchild);
        }
    }
}
